There is a growing use of data compression techniques in data storage and communication systems because data compression can minimize the amount of storage space or transmission bandwidth required to convey information.
Data compressed by a "lossy" technique cannot be recovered perfectly by any decompression technique because some information is lost during compression, but data compressed by a "lossless" technique can be recovered perfectly. Quantization is one well known example of a lossy technique. Run-length encoding (RLE) is a well known example of a lossless technique. In some audio and video applications, systems often use both lossy and lossless compression techniques.
Some "perceptual coders" of signals intended for human perception attempt to apply lossy compression techniques according to psycho-perceptual principles such that the effects of the compression loss is imperceptible. Generally the amount of loss increases with higher levels of lossy compression; therefore, there are limits to how much lossy compression can be applied before the subjective quality of the resultant signal is degraded. Some perceptual coders also apply lossless techniques in addition to lossy techniques to achieve further compression without incurring perceivable degradation.
A perceptual coding standard which includes the application of lossless compression to quantized information is described in the ISO/MPEG standards document "Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbit/s-CD 11172-3 (Part 3 Audio)," ISO/IEC JTCI/SC29, 1992, which is incorporated herein by reference in its entirety. An example of a transform coder which applies Huffman coding, a lossless compression technique, to quantized transform coefficients is described in U.S. Pat. No. 5,285,498 which is incorporated herein by reference in its entirety.
Huffman coding is a well known lossless compression technique. Various implementations of Huffman coding frequently use one or more tables or matrices. During compression, one or more data symbols to be compressed are used as keys into an appropriate encoding table; the encoding table provides the appropriate variable-length code word. During decompression, the variable-length code word is used to traverse a tree-like structure stored in one or more decoding tables to establish the original value of the compressed symbols. In many practical embodiments, the encoding and decoding tables are stored in Read Only Memory (ROM) or in Random Access Memory (RAM). Unfortunately, these coding tables are generally very large and require considerable memory, thereby increasing implementation costs. It is desirable to minimize the amount of memory required to store and use coding tables.